package com.cplatform.cat;

import java.util.HashMap;

/**
 * Hello world!
 *
 */
public class App 
{
    public static void main( String[] args )
    {
//        int[] height = {1,8,6,2,5,4,8,3,7};
//        maxArea(height);
//        int[] nums = {1,2,0,3,4,5};
//        System.out.println(sum(nums,nums.length));
//        moveZeroes(nums);
//        Long s = System.currentTimeMillis();
        int  f =  fibr(40);
//        Long e = System.currentTimeMillis();
//        System.out.println("f="+f+",耗时"+(e-s));
    }
    public static int maxArea(int[] height) {
        int max = 0;
        for(int i = 0,j = height.length-1;i<j;){
            int minHeight = height[i] < height[j] ? height[i++]:height[j--];
            int area = (j-i+1) * minHeight;
            max = Math.max(area,max);
        }
        return max;
    }

    public static void moveZeroes(int[] nums) {
        int j = 0;
        for(int i = 0;i<nums.length;i++){
            if(nums[i]!=0){
                nums[j] = nums[i];
                if(i!=j){
                    nums[i] = 0;
                }
                j++;
            }
        }
    }
    static HashMap<Integer,Integer> cache = new HashMap<>();
    public static int fib(int N) {
        if( N == 1 || N == 2){
            return 1;
        }
        if (cache.get(N)!=null){
            return cache.get((N));
        }
        cache.put(N,fib(N-1)+fib(N-2));
        return cache.get(N);
    }

    public static int fibr(int N){
        if (N == 1||N == 2){
            return 1;
        }
        return fibr(N-1)+fibr(N-2);
    }

    /**
     * 数组求和
     */
    public  static int sum(int[] a,int len){
        if (len == 0){
            return 0;
        }
        return a[len-1] + sum(a,len-1);
    }

    /**
     * 反转字符串
     */
    public static void helper(int left,int right,char[] s){
        if(left>=right){
            return;
        }
        char tmp = s[left];
        s[left] = s[right];
        s[right] = tmp;
        helper(left+1,right-1,s);
    }
}
